최소직사각형

NOTE

프로그래머스 · 구현(“정렬 후 최대값” 패턴) 여러 명함을 모두 담는 최소 지갑 크기를 구하는 문제. 각 카드의 긴 변을 가로로 맞춘 뒤, 가로 최댓값 × 세로 최댓값이 답. O(N).

📝 문제

• 명함들의 크기 sizes[i] = {w, h}가 주어질 때, 모든 명함을 담을 수 있는 가장 작은 지갑의 넓이를 구한다.
• 명함은 회전 가능하므로 각 카드에서 작은 값을 가로, 큰 값을 세로로 정렬해도 된다.

💡 접근

• 핵심: “각 카드의 긴 변을 세로로 맞추고, 그 중 가로 최댓값 × 세로 최댓값”.
• 즉 이 문제의 본질은 “2차원 배열에서 각 행을 정렬하고, 각 열의 최대값을 구하는” = “정렬 후 최대값” 패턴.
• swap 대신 Math.min/Math.max를 쓰면 원본 배열을 건드리지 않고 가독성도 좋다.

⌨️ 풀이

public int solution(int[][] sizes) {
    int maxW = 0;
    int maxH = 0;
 
    for (int i = 0; i < sizes.length; i++) {
        int w = Math.min(sizes[i][0], sizes[i][1]);
        int h = Math.max(sizes[i][0], sizes[i][1]);
 
        maxW = Math.max(maxW, w);
        maxH = Math.max(maxH, h);
    }
 
    return maxW * maxH;
}

개선 포인트: swap 대신 Math.min/Math.max 사용, 원본 배열 미변경, 가독성 향상.

⏱️ 복잡도

• 시간: O(N) — N(최대 10,000) 한 번 순회, 별도 정렬 없음.
• 공간: O(1).

📎 확장 사고

• 이 패턴은 명함·박스 정렬·회전 후 최대 면적 문제로 확장된다.
• 카드가 3차원({w, h, d})이라면? → 모든 카드를 담는 최소 박스 부피를 구하는 사고력 문제로 승격된다.

---

🔗 관련

• (Algorithm) 바탕화면정리 - 핵심 개념 및 특징 정리
• (Algorithm) 카펫 - 핵심 개념 및 특징 정리 — 사각형/격자 계열
• (Algorithm) 60일 계획 - 핵심 개념 및 특징 정리 — 1~20일차 학습 커리큘럼에서 참조하는 문제